#include <stdio.h>
#include <string.h>

#define STDIN
//#define DEBUG

int cash;
int N;
int dk[15];
int nk[15];

int dp[100005];

#define max(a, b) (a) > (b) ? (a) : (b)
void ZeroOnePack(int cost, int weight)
{
    int v;
    for (v = cash; v >= cost; v--)
    {
        dp[v] = max(dp[v], dp[v-cost] + weight);
    }
}

void CompletePack(int cost, int weight)
{
    int v;
    for (v = cost; v <= cash; v++)
    {
        dp[v] = max(dp[v], dp[v-cost] + weight);
    }
}

void MultiplePack(int cost, int weight, int amount)
{
    if (amount * cost >= cash)
    {
        CompletePack(cost, weight);
        return;
    }
    int k = 1;
    while(k < amount)
    {
        ZeroOnePack(k*cost, k*weight);
        amount -= k;
        k *= 2;
    }
    ZeroOnePack(amount*cost, amount*weight);
}

int main()
{
#ifdef STDIN
    freopen("bin/1276.in", "r", stdin);
#endif
    while(1)
    {
        if(scanf("%d", &cash) == EOF)
            break;
        scanf("%d", &N);
        int i;
        for (i = 0; i < N; ++i)
        {
            scanf("%d %d", &nk[i], &dk[i]);
        }

        memset(dp, 0, sizeof(dp));

        for (i = 0; i < N; ++i)
        {
#ifdef DEBUG
            printf("cost: %d weight: %d amount: %d\n", dk[i], dk[i], nk[i]);
#endif
            MultiplePack(dk[i], dk[i], nk[i]);
        }
#if 0
        for (i = 0; i <= cash; ++i)
            printf("%d\t", dp[i]);
        printf("\n=================\n");
#endif
        printf("%d\n", dp[cash]);

    }
    return 0;
}
